package formal.linkedList;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

/**
 * 回文链表
 *
 * @author DengYuan2
 * @create 2021-01-08 20:50
 */
public class E_234 {
    public static void main(String[] args) {
        ListNode n1 = new ListNode(1);
        ListNode n2 = new ListNode(2);
        ListNode n3 = new ListNode(1);
//        ListNode n4 = new ListNode(1);
//        ListNode n5 = new ListNode(3);
        n1.next = n2;
        n2.next = n3;
//        n3.next = n4;
//        n4.next = n5;
        boolean palindrome = isPalindrome5(n1);
        System.out.println(palindrome);

    }

    /**
     * 我的写法1-放进list，比较list倒过来是否还是一样
     * 这种方法不太好
     *
     * @param head
     * @return
     */
    public static boolean isPalindrome(ListNode head) {
        ListNode node = head;
        List<Integer> list = new ArrayList<>();
        while (node != null) {
            list.add(node.val);
            node = node.next;
        }
        List<Integer> listNodes = new ArrayList<>(list.size());
        listNodes.addAll(list);
        Collections.reverse(listNodes);
        for (int i = 0; i < list.size(); i++) {
            if (!list.get(i).equals(listNodes.get(i))) {
                return false;
            }
        }


        return true;
    }

    /**
     * 我的写法2-将链表分成两半，将后面一半反转，与前面的比较
     *
     * @param head
     * @return
     */
    public static boolean isPalindrome2(ListNode head) {
        ListNode node = head;
        int size = 0;
        while (node != null) {
            size++;
            node = node.next;
        }
        node = head;
        int count = (size % 2 == 1) ? size / 2 + 1 : size / 2;
        for (int i = 0; i < count; i++) {
            node = node.next;
        }
        //node为第二段的头节点
        ListNode tmp = node;
        ListNode listNode = new ListNode(-1);
        while (tmp != null) {
            ListNode cur = tmp.next;
            tmp.next = listNode.next;
            listNode.next = tmp;
            tmp = cur;
        }
        listNode = listNode.next;
        int i = 0;
        while (i < size / 2) {
            if (listNode.val != head.val) {
                return false;
            }
            i++;
            listNode = listNode.next;
            head = head.next;
        }
        return true;
    }

    /**
     * 大神—想法类似我的写法2，但分成一半的方式不一样
     *
     * @param head
     * @return
     */
    public static boolean isPalindrome3(ListNode head) {
        if (head == null || head.next == null) {
            return true;
        }
        // 1 2 3 4
        ListNode slow = head;
        ListNode fast = head.next;
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }
//        //第二部分的长度<=第一部分的长度，后者最多比前者长1
//        slow=slow.next;
        //

        //将链表切成两部分
        ListNode tmp = head;
        while (tmp.next != slow) {
            tmp = tmp.next;
        }
        tmp.next = null;

        //反转第二部分的链表
        ListNode node = null;
        ListNode tmpNode = slow;
        while (slow != null) {
            tmpNode = slow.next;
            slow.next = node;
            node = slow;
            slow = tmpNode;
        }
        //此时node为第二部分的头节点
        while (node != null) {
            if (node.val != head.val) {
                return false;
            }
            node = node.next;
            head = head.next;
        }
        return true;
    }

    /**
     * 官方1-将值复制到数组中后用双指针法检查数组
     * 比较慢
     * 时间复杂度为O(n)
     * @param head
     * @return
     */
    public static boolean isPalindrome4(ListNode head) {
        List<Integer> list = new ArrayList<>();
        while (head != null) {
            list.add(head.val);
            head = head.next;
        }
        for (int i = 0, j = list.size() - 1; i <= j; i++, j--) {
            if (!list.get(i).equals(list.get(j))) {
                return false;
            }
        }
        return true;
    }

    /**
     * 官方2-递归
     * 比上一种更慢
     * 时间复杂度：O(n)   空间复杂度：O(n)
     * @param head
     * @return
     */
    private static ListNode front = null;
    public static boolean isPalindrome5(ListNode head) {
        front=head;
        return compareHelper(head);
    }

    public static boolean compareHelper(ListNode cur){
        if (cur!=null){
            if (!compareHelper(cur.next)){
                return false;
            }
            if (cur.val!=front.val){
                return false;
            }
            front=front.next;
        }
        return true;
    }



}
